package twobranchsearch.kthlargest;

import java.util.Stack;

/**
 * @Date 2020/03/13
 * @author 王光浩
 * @Thinking 使用二叉搜索树。
 * @Analysis 时间复杂度O（nlogn+logn+logn）
 */
public class MyMethodTwo {
	private TreeNode root;
	private int kk;
	public MyMethodTwo(int k, int[] nums) {
		root=buildTree(nums);
		kk=k;
    }
    
    public int add(int val) {
    	root=insert(val,root);
    	return findK(0,root);
    }
    //在二叉搜索树中找到目标
    private int findK(int kth,TreeNode root) {
    	int right=root.right==null?0:root.right.count;
    	right+=kth;
    	if(right+1==kk)return root.val;
    	else if(right<kk)return findK(right+1,root.left);
    	else return findK(kth,root.right);
    }
    //构建一颗搜索二叉树
    private TreeNode buildTree(int[] nums) {
    	if(nums.length==0)return null;
    	TreeNode root=new TreeNode(nums[0]);
    	for(int i=1;i<nums.length;i++)
    		insert(nums[i],root);
    	return root;
    }
    private TreeNode insert(int val,TreeNode root) {
    	if(root==null)return new TreeNode(val);
    	if(root.val==val) {
    		TreeNode left=new TreeNode(val);
    		int count=root.left==null?0:root.left.count;
    		left.left=root.left;
    		root.left=left;
    		left.count+=count;
    	}
    	else if(root.val>val)root.left=insert(val,root.left);
    	else root.right=insert(val,root.right);
    	root.count++;
    	return root;
    }
}
/**
 * @Date 2020/03/13
 * @author 王光浩
 * @Description 节点信息类
 */
class TreeNode{
	TreeNode left=null;
	TreeNode right=null;
	int val;
	int count=1;   //该节点所在子树中所有节点的数目
	public TreeNode(int val) {
		this.val=val;
	}
}